package com.aug_leo.datastructure.linkedlist;

/**
 * 合并两个有序链表
 */
public class E06Leetcode21 {

    /**
     * <h3>方法一</h3>
     * 1、谁小，谁把链给 pointer，pointer和小的都向后平移一位
     * 2、当 pointer1、pointer2有一个为null，退出循环，把不为null的链给 pointer
     *
     * @param pointer1 第一个链表的头节点
     * @param pointer2 第二个链表的头节点
     * @return 合并后的链表头节点
     */
    public ListNode mergeTwoLists1(ListNode pointer1, ListNode pointer2) {
        // 创建一个哨兵节点作为合并后链表的头部
        ListNode sentinel = new ListNode(-1, null);
        // 初始化一个指针指向哨兵
        ListNode pointer = sentinel;

        // 遍历两个链表直到一个为null
        while (pointer1 != null && pointer2 != null) {
            // 比较两个链表当前节点的值，选择较小的一个继续合并
            if (pointer1.val < pointer2.val) {
                // 如果第一个链表当前节点的值比较小，将其链接到合并后的链表
                pointer.next = pointer1;
                // 将第一个链表的指针向后移动
                pointer1 = pointer1.next;

            } else {
                // 如果第二个链表当前节点的值较小或相等，将其链接到合并后的链表
                pointer.next = pointer2;
                // 将第二个链表的指针向后移动
                pointer2 = pointer2.next;

            }
            // 将合并后的链表指针向后移动
            pointer = pointer.next;
        }

        // 当第一个链表遍历完成后，直接将另一个链表剩余的部分链接到合并后的链表末尾
        if (pointer1 != null) {
            pointer.next = pointer1;
        }

        if (pointer2 != null) {
            pointer.next = pointer2;
        }

        // 返回合并后链表的头节点
        return sentinel.next;
    }

    /*
            public ListNode mergeTwoLists(ListNode pointer1=[1, 3, 8, 9], ListNode pointer2 = [2, 4]) {
                public ListNode mergeTwoLists(ListNode pointer1=[3, 8, 9], ListNode pointer2 = [2, 4]) {
                    public ListNode mergeTwoLists(ListNode pointer1=[3, 8, 9], ListNode pointer2 = [4]) {
                        public ListNode mergeTwoLists(ListNode pointer1=[8, 9], ListNode pointer2 = [4]) {
                            public ListNode mergeTwoLists(ListNode pointer1=[8, 9], ListNode pointer2 = null) {
                                return [8, 9];
                            }
                            4.next = [8, 9];
                            return 4;
                        }
                        3.next = 4;
                        return 3;
                    }
                    2.next = 3;
                    return 2;
                }
                1.next = 2;
                return 1;
            }

     */

    /**
     * <h3>方法二 递归</h3>
     * 递归函数应该返回
     * · 更小的那个链表节点，并把它剩余节点与另一个链表再次递归
     * · 返回之前更新此节点的 next
     *
     * @param pointer1 第一个链表的头节点
     * @param pointer2 第二个链表的头节点
     * @return 合并后的链表头节点
     */
    public ListNode mergeTwoLists(ListNode pointer1, ListNode pointer2) {

        if (pointer1 == null) {
            return pointer2;
        }

        if (pointer2 == null) {
            return pointer1;
        }

        if (pointer1.val < pointer2.val) {
            pointer1.next = mergeTwoLists(pointer1.next, pointer2);
            return pointer1;
        } else {
            pointer2.next = mergeTwoLists(pointer1, pointer2.next);
            return pointer2;
        }
    }

    public static void main(String[] args) {
        ListNode pointer1 = ListNode.of(1, 3, 8, 9);
        ListNode pointer2 = ListNode.of(2, 4);
        System.out.println(new E06Leetcode21()
                .mergeTwoLists(pointer1, pointer2));
    }
}
